Now that we've seen a complete run-through of Prim's algorithm, let's test your understanding of its core decision-making step. The graph on the right shows a partially constructed Minimum Spanning Tree.
- Your task is to identify which edge Prim's algorithm will select next.
- Remember the core rule: The algorithm greedily chooses the lightest-weight edge that connects a vertex in the MST set to a vertex outside the set, without creating a cycle.
- Examine the frontier edges (the dashed orange lines) and choose the one with the minimum weight.
| Option | Edge | Weight |
|---|---|---|
| A | (B, C) | 1 |
| B | (C, D) | 2 |
| C | (B, D) | 5 |
| D | (E, F) | 9 |